#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define MAX_LEVEL	32
#define SKIP_LIST_P 0.25

#define ASSERT(p)	do{if (!(p)) _exit(-1);}while(0);

typedef struct _SkipNode{
	int data;
	struct _SkipNode** forward;
}SkipNode;

typedef struct {
	int level;
	SkipNode* head;
}SkipList;

int getRandomLevel(){
	int level = 1;
	while ((random() & 0xFFFF) < 0xFFFF*SKIP_LIST_P){
		level = level + 1;
	}

	return level < MAX_LEVEL ? level:MAX_LEVEL;
}

void printSkipList(SkipList* list){
	SkipNode* p = NULL;
	int i = 0, l = list->level;
	printf("-------------this is a skipList instance-------------\n");
	printf("-------------MaxLevel=%d-------------\n", list->level);
	for (i = l-1; i >= 0; --i){
		p = list->head->forward[i];

		printf("level[%d]:", i);
		while (p){
			printf("\t%d",p->data);
			p = p->forward[i];
		}
		printf("\n");
	}
}

SkipNode* createSkipNode( int value, int level){
	int i = 0;
	SkipNode* node = NULL;

	node = (SkipNode* )malloc(sizeof(SkipNode));
	ASSERT(node!=NULL);	
	node->forward = (SkipNode**)malloc(level*sizeof(SkipNode*));
	ASSERT(node->forward);
	for (i = 0; i < level; i++){
		node->forward[i] = NULL;
	}

	node->data = value;
	return node;
}

void insertSkipNode(SkipList* list, int data){
	int level = getRandomLevel();
	SkipNode* node = createSkipNode(data, level);
	SkipNode* p = NULL;
	SkipNode* q = NULL;
	int i = 0;

	if ( level > list->level ){
		list->level = level;
	}

	for (i = level-1; i >= 0; i--){
		q = list->head;
		p = list->head->forward[i];
		while (p){
			if (p && (p->data < data) ){
				q = p;
				p = p->forward[i];
			} else {
				break;
			}
		}
		q->forward[i] = node;
		node->forward[i] = p;
	}
}

SkipNode* findNode(SkipList* list, int data){
	SkipNode* p = NULL;
	SkipNode* pe = NULL;
	SkipNode* pb = NULL;
	SkipNode* q = NULL;
	int found = 0;
	int i = 0, l = list->level;
	pb = list->head;
	for (i = l-1; i >= 0; --i){
		p = pb->forward[i];
		while (p && p != pe){
			if (p->data == data){
				printf("Trace(%d):found level=%d,data=%d\n",data, i, p->data);
				q = p;
				found = 1;
				break;
			} else if (p->data < data) {
				printf("Trace(%d):begin level=%d,data=%d\n",data, i, p->data);
				pb = p;
				p = p->forward[i];
			} else {
				printf("Trace(%d):end level=%d,data=%d\n",data, i, p->data);
				pe = p;
				break;
			}
		}
		if (pb == pe){
			break;
		}
		if (found){
			printf("data(%d) is found!\n", data);
			return q;
		}
	}

	printf("data(%d) isn't found!\n", data);
	return q;
}

void freeNode() {
}

void deleteNode(){
}

int main()
{
	int i = 0;
	SkipList* list = (SkipList*)malloc(sizeof(SkipList));
	ASSERT(list != NULL);
	list->level = 0;
	list->head = createSkipNode(-1,32);
	
	for (i = 0; i < 100; i++){
		insertSkipNode(list, i);
	}
	
	printSkipList(list);

	for (i = 0; i < 5; i++)
	{
		findNode(list, random()%200);
	}

	return 0;
}
